package math;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class BasicCalculator224 {

    @Test
    public void test1() {
        calculate("1 + 1");//7
        calculate("3+2*2");//7
        calculate("-3+2*2+1");//2
        calculate("-3+2*(2+1)");//3
        calculate("-3+(+2*1)*((-2*4+1)+1)");//-15
    }

    static final Map<Character, Integer> map = new HashMap<Character, Integer>(){{
        put('-', 1);
        put('+', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};

    public int calculate(String s) {
        Stack<Integer> nums = new Stack<>();
        Stack<Character> oprs = new Stack<>();
        // 必须要去除空格, 否则 判断 "(+" 等情况有问题
        s = s.replace(" ", "");
        char[] c = s.toCharArray();
        int i = 0;
        while (i < s.length()) {
            if (Character.isDigit(c[i])) {
                int d = 0;
                while (i < s.length() && Character.isDigit(c[i])) {
                    d = d * 10 + (c[i] - '0');
                    i++;
                }
                nums.push(d);
            } else if (c[i] == '(') {
                oprs.push(c[i]);
                i++;
            } else if (c[i] == ')') {
                // 一直计算到上一个')'
                while (!oprs.isEmpty() && oprs.peek() != '(') {
                    calculate(nums, oprs);
                }
                // 弹出'('
                if (!oprs.isEmpty() && oprs.peek() == '(') {
                    oprs.pop();
                }
                i++;
            } else { // c[i]为加减乘除
                if (c[i] == '+' || c[i] == '-') {
                    // "(+" -> "(0+"
                    // "(-" -> "(0-"
                    // "$+" -> "$0+"
                    // "$-" -> "$0-"
                    if ((i-1 >= 0 && c[i-1] == '(') || i == 0) {
                        nums.push(0);
                    }
                }
                // opr入栈前, 先尝试执行栈内高优先级或平优先级的运算
                while (!oprs.isEmpty() && oprs.peek() != '(') {
                    Character prevOpr = oprs.peek();
                    // 注意这里是">=", 不能是">"
                    if (map.get(prevOpr) >= map.get(c[i])) {
                        calculate(nums, oprs);
                    } else {
                        break;
                    }
                }
                oprs.push(c[i]);
                i++;
            }
        }
        while (!oprs.isEmpty()) {
            calculate(nums, oprs);
        }
        System.out.format("%s = %d\n", s, nums.peek());
        return nums.pop();
    }

    void calculate(Stack<Integer> nums, Stack<Character> oprs) {
        if (nums.size() < 2 || oprs.size() < 1) {
            return;
        }
        int b = nums.pop();
        int a = nums.pop();
        char op = oprs.pop();
        int ans = 0;
        if (op == '+') ans = a + b;
        else if (op == '-') ans = a - b;
        else if (op == '*') ans = a * b;
        else if (op == '/')  ans = a / b;
        else if (op == '^') ans = (int)Math.pow(a, b);
        else if (op == '%') ans = a % b;
        nums.push(ans);
    }

}
